Théorème de Bachet-Bézout

Théorème

Soit $a\in \mathbb{Z}$ et $b\in \mathbb{Z}$ non nuls. Soit $d\in \mathbb{Z}$ .
$d=\mathrm{PGCD}(a;b)$ si, et seulement si, $\{\begin{array}{l}d\text{ divise }a\\ d\text{ divise }b\\ \text{il existe }(u;v)\in {\mathbb{Z}}^2\text{ tel que }au+bv=d.\end{array}$  

Remarques

• Ce théorème généralise le théorème de Bézout, qui est le cas particulier où $d=1$ .
• L'égalité $au+bv=d=\mathrm{PGCD}(a;b)$ est appelée une identité de Bézout. Pour déterminer un couple  $(u;v)\in {\mathbb{Z}}^2$ qui satisfait cette égalité, on peut utiliser la méthode de remontée de l'algorithme d'Euclide.
  

Démonstration

On procède par double implication.

$[\Rightarrow ]$ Supposons que $d=\mathrm{PGCD}(a;b)$ .
D'après la propriété caractéristique du PGCD, il existe $(a^{\prime };b^{\prime })\in {\mathbb{Z}}^2$ tel que $a=a^{\prime }d$ , $b=b^{\prime }d$ et $\mathrm{PGCD}(a^{\prime };b^{\prime })=1$ . Par conséquent, $d$ divise $a$ et $b$ .
De plus, d'après le théorème de Bézout, il existe $(u;v)\in {\mathbb{Z}}^2$ tel que $a^{\prime }u+b^{\prime }v=1$ .
En multipliant cette égalité par $d>0$ , on obtient : $\begin{array}{r}{a}^{\prime }du+b^{\prime }dv=d⟺au+bv=d.\end{array}$

$[\Leftarrow ]$ Supposons que $d$ divise $a$ et $b$ , et qu'il existe $(u;v)\in {\mathbb{Z}}^2$ tel que $au+bv=d$ .
Soit $k\in \mathcal{D}(a;b)$ . Comme $k$ divise $a$ et $b$ , $k$ divise toute combinaison linéaire de $a$ et $b$ , notamment $au+bv$ , donc $k$ divise $d$ .

On en déduit que $k⩽d$ et ainsi, l'ensemble $\mathcal{D}(a;b)$ est majoré par $d$ .
Or $d$ divise $a$ et $b$ , donc $d\in \mathcal{D}(a;b)$ , ce qui prouve que $d$ est le plus grand élément de $\mathcal{D}(a;b)$ , c'est-à-dire $d=\mathrm{PGCD}(a;b)$ .